{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6c7866b6-48bf-44be-adbb-76773a5cc642",
   "metadata": {},
   "source": [
    "### PR代码练习: Numpy数组元素排序: KNN"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8afa9805-81fe-477c-940d-2276aabf38a1",
   "metadata": {},
   "source": [
    "#### 题目一：求得5个随机点每两点距离的按行排序列表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "c3cd9187-ef6c-4c2e-9407-1b143233b8e7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "一共生成介于[0,255)的 5 个随机点(seed=30)\n",
      " [[ 37 165]\n",
      " [173  45]\n",
      " [244 140]\n",
      " [151 130]\n",
      " [ 53 251]] \n",
      "\n",
      "每两点之间的距离平方列表:\n",
      " [[    0 32896 43474 14221  7652]\n",
      " [32896     0 14066  7709 56836]\n",
      " [43474 14066     0  8749 48802]\n",
      " [14221  7709  8749     0 24245]\n",
      " [ 7652 56836 48802 24245     0]] \n",
      "\n",
      "每一行都按照距离排序后的索引值列表:\n",
      " [[0 4 3 1 2]\n",
      " [1 3 2 0 4]\n",
      " [2 3 1 0 4]\n",
      " [3 1 2 0 4]\n",
      " [4 0 3 2 1]]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "r = np.random.RandomState(seed=30)\n",
    "n = 5 # 随机点数目\n",
    "x = r.randint(0,255,(n,2)) # 生成5个坐标值介于[0,255)的随机点\n",
    "\n",
    "########## 请只修改此范围以内代码 #########\n",
    "h,w=x.shape\n",
    "x1= x.reshape(h,1,w) # 想办法改变x的结构\n",
    "x2= x.reshape(1,h,w)\n",
    "\n",
    "s = np.sum((x1-x2)**2,axis=2) # 距离的平方列表\n",
    "d = np.argsort(s) # 距离排序后索引值列表\n",
    "########################################\n",
    "\n",
    "print(\"一共生成介于[0,255)的\",n,\"个随机点(seed=30)\\n\",x,\"\\n\")\n",
    "print(\"每两点之间的距离平方列表:\\n\",s,\"\\n\")\n",
    "print(\"每一行都按照距离排序后的索引值列表:\\n\",d)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8409ea9e-5f3f-41e9-9182-0e36b56f888c",
   "metadata": {},
   "source": [
    "#### 题目二：从100个随机点中选择5个点，列出其最近邻NN和最远邻FN"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "142c302b-b6ee-4e46-9f65-fbd606d7dac2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Collecting prettytable\n",
      "  Downloading prettytable-3.4.1-py3-none-any.whl (26 kB)\n",
      "Requirement already satisfied: wcwidth in /opt/conda/lib/python3.9/site-packages (from prettytable) (0.2.5)\n",
      "Installing collected packages: prettytable\n",
      "Successfully installed prettytable-3.4.1\n"
     ]
    }
   ],
   "source": [
    "!pip install prettytable"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "0811cab7-d42e-4c04-9281-2fb184c8f514",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "从 100 个随机点中随机挑选 5 个点\n",
      "选中的点的索引值列表为:  [18 60 87 85 44]\n",
      "选中的点的列表为:  [(15, 151), (159, 108), (82, 81), (160, 14), (188, 204)]\n",
      "+-----------+-----------+-----------+\n",
      "| points    | NN        | FN        |\n",
      "+-----------+-----------+-----------+\n",
      "| [ 15 151] | [ 19 158] | [228  13] |\n",
      "| [159 108] | [150 124] | [ 18 244] |\n",
      "| [82 81]   | [91 78]   | [226 250] |\n",
      "| [160  14] | [163  18] | [ 18 244] |\n",
      "| [188 204] | [175 206] | [ 9 11]   |\n",
      "+-----------+-----------+-----------+\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from prettytable import PrettyTable\n",
    "\n",
    "r = np.random.RandomState(seed=30) \n",
    "n = 100\n",
    "x = r.randint(0,255,(n,2))       # 生成100个随机点\n",
    "nc = 5\n",
    "c = r.choice(n,nc,replace=False)  # 生成从0到100中随机选择5个点的索引值列表\n",
    "\n",
    "########## 请只修改此范围以内代码 #########\n",
    "h,w=x.shape\n",
    "x1= x.reshape(h,1,w) # 想办法改变x的结构\n",
    "x2= x.reshape(1,h,w)\n",
    "\n",
    "s = np.sum((x1-x2)**2,axis=2) # 距离的平方列表\n",
    "d = np.argsort(s) # 距离排序后索引值列表\n",
    "\n",
    "NN_index = d[c, 1]    #求5个点的最近点，，在原数组中的位置\n",
    "FN_index = d[c, -1]    #求5个点的最远点，，在原数组中的位置\n",
    "\n",
    "points = x[c, :]    #选择的5个点\n",
    "NN = x[NN_index, :]    #每个点的最近点\n",
    "FN = x[FN_index, :]    #每个点的最远点\n",
    "\n",
    "\n",
    "result= np.stack((points, NN, FN), axis=1)    #包含所有所有结果的 numpy 数组\n",
    "########################################\n",
    "\n",
    "print(\"从 {0} 个随机点中随机挑选 {1} 个点\".format(n,nc))\n",
    "print(\"选中的点的索引值列表为: \",c)\n",
    "print(\"选中的点的列表为: \",[(x,y) for (x,y) in x[c,:]])\n",
    "tb = PrettyTable()\n",
    "tb.field_names=['points','NN','FN']\n",
    "tb.align='l' # 左对齐\n",
    "for i in result:\n",
    "    tb.add_row(i)\n",
    "\n",
    "print(tb)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3751cec3-1352-4b09-8ef2-c08d9dd2bc3a",
   "metadata": {},
   "source": [
    "#### 参考答案"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "ac950538-36ae-4c8e-b5f0-300e28df5074",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "从 100 个随机点中随机挑选 5 个点\n",
      "选中的点的索引值列表为:  [18 60 87 85 44]\n",
      "选中的点的列表为:  [(15, 151), (159, 108), (82, 81), (160, 14), (188, 204)]\n",
      "+-----------+-----------+-----------+\n",
      "| points    | NN        | FN        |\n",
      "+-----------+-----------+-----------+\n",
      "| [ 15 151] | [ 19 158] | [228  13] |\n",
      "| [159 108] | [150 124] | [ 18 244] |\n",
      "| [82 81]   | [91 78]   | [226 250] |\n",
      "| [160  14] | [163  18] | [ 18 244] |\n",
      "| [188 204] | [175 206] | [ 9 11]   |\n",
      "+-----------+-----------+-----------+\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from prettytable import PrettyTable\n",
    "\n",
    "r = np.random.RandomState(seed=30)\n",
    "n = 100\n",
    "x = r.randint(0, 255, (n, 2))       # 生成100个随机点\n",
    "nc = 5\n",
    "c = r.choice(n, nc, replace=False)  # 生成从0到100中随机选择5个点的索引值列表\n",
    "\n",
    "########## 请只修改此范围以内代码 #########\n",
    "h, w = x.shape\n",
    "x1 = x.reshape(h, 1, w)\n",
    "x2 = x.reshape(1, h, w)\n",
    "s = np.sum((x1-x2)**2, axis=2)\n",
    "d = np.argsort(s, axis=1)\n",
    "# 以上代码得到每一个点按距离排序的索引值矩阵 d 【100行，100列】\n",
    "\n",
    "c_list = x[c] # 得到随机选择的所有点的列表\n",
    "NN_list = x[d[c, 1]] # 在索引值矩阵d中获得所有选中的点的最近邻，即表示那些点的那一行的第二个元素\n",
    "FN_list = x[d[c, -1]]  # 在索引值矩阵d中获得所有选中的点的最近邻，即表示那些点的那一行的最后一个元素\n",
    "\n",
    "result = np.stack((c_list, NN_list, FN_list), axis=1)\n",
    "########################################\n",
    "\n",
    "print(\"从 {0} 个随机点中随机挑选 {1} 个点\".format(n, nc))\n",
    "print(\"选中的点的索引值列表为: \", c)\n",
    "print(\"选中的点的列表为: \", [(x, y) for (x, y) in x[c, :]])\n",
    "tb = PrettyTable()\n",
    "tb.field_names = ['points', 'NN', 'FN']\n",
    "tb.align = 'l'  # 左对齐\n",
    "for i in result:\n",
    "    tb.add_row(i)\n",
    "\n",
    "print(tb)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "da27e821-2a9d-485b-b976-e5c15100a565",
   "metadata": {},
   "source": [
    "#### 题目三：从100个随机点中选择5个点，列出其最近邻NN，与最近邻的距离，最远邻FN，与最远邻之间的距离"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "0acdbf50-1063-4bad-98ae-3f0ed8136502",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "从 100 个随机点中随机挑选 5 个点\n",
      "选中的点的索引值列表为:  [18 60 87 85 44]\n",
      "选中的点的列表为:  [(15, 151), (159, 108), (82, 81), (160, 14), (188, 204)]\n",
      "+---------------+---------------+---------------------+---------------+----------------------+\n",
      "| points        | NN            | NN Distance         | FN            | FN Distance          |\n",
      "+---------------+---------------+---------------------+---------------+----------------------+\n",
      "| ['15' '151']  | ['19' '158']  | ['18<->38' '8.06']  | ['228' '13']  | ['18<->19' '253.80'] |\n",
      "| ['159' '108'] | ['150' '124'] | ['60<->97' '18.36'] | ['18' '244']  | ['60<->11' '195.90'] |\n",
      "| ['82' '81']   | ['91' '78']   | ['87<->23' '9.49']  | ['226' '250'] | ['87<->72' '222.03'] |\n",
      "| ['160' '14']  | ['163' '18']  | ['85<->10' '5.00']  | ['18' '244']  | ['85<->11' '270.30'] |\n",
      "| ['188' '204'] | ['175' '206'] | ['44<->73' '13.15'] | ['9' '11']    | ['44<->48' '263.23'] |\n",
      "+---------------+---------------+---------------------+---------------+----------------------+\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from prettytable import PrettyTable\n",
    "\n",
    "r = np.random.RandomState(seed=30) \n",
    "n = 100\n",
    "x = r.randint(0,255,(n,2))       # 生成100个随机点\n",
    "nc = 5\n",
    "c = r.choice(n,nc,replace=False)  # 生成从0到100中随机选择5个点的索引值列表\n",
    "\n",
    "########## 请只修改此范围以内代码 #########\n",
    "h,w=x.shape\n",
    "x1= x.reshape(h,1,w) # 想办法改变x的结构\n",
    "x2= x.reshape(1,h,w)\n",
    "\n",
    "s = np.sum((x1-x2)**2,axis=2) # 距离的平方列表\n",
    "d = np.argsort(s) # 距离排序后索引值列表\n",
    "\n",
    "NN_index = d[c, 1]    #求5个点的最近点，在原数组中的位置\n",
    "FN_index = d[c, -1]    #求5个点的最远点，在原数组中的位置\n",
    "\n",
    "points = x[c, :]    #选择的5个点\n",
    "NN = x[NN_index, :]    #每个点的最近点\n",
    "FN = x[FN_index, :]    #每个点的最远点\n",
    "\n",
    "NN_Distance = []\n",
    "FN_Distance = []\n",
    "for i in range(0,5):\n",
    "    str1=f'''{c[i]}<->{NN_index[i]}'''    #生成所对应的字符串 \n",
    "    str2=f'''{c[i]}<->{FN_index[i]}'''\n",
    "    NN_distance=(format(np.sqrt(s[c[i], NN_index[i]]), '.2f'))    #求距离并保留两位小数\n",
    "    FN_distance=(format(np.sqrt(s[c[i], FN_index[i]]), '.2f'))\n",
    "    NN_Distance.append(str1)   \n",
    "    NN_Distance.append(NN_distance)  #将字符串和距离分别加入空列表\n",
    "    FN_Distance.append(str2)\n",
    "    FN_Distance.append(FN_distance)\n",
    "NN_Distance=(np.array(NN_Distance)).reshape(5,-1)     #转化为numpy数组\n",
    "FN_Distance=(np.array(FN_Distance)).reshape(5,-1)\n",
    "\n",
    "\n",
    "#将 points, NN, NN Distance, FN, FN Distance 连接起来，用于美化矩阵\n",
    "result = np.stack((points, NN, NN_Distance, FN, FN_Distance), axis=1) \n",
    "\n",
    "########################################\n",
    "\n",
    "print(\"从 {0} 个随机点中随机挑选 {1} 个点\".format(n,nc))\n",
    "print(\"选中的点的索引值列表为: \",c)\n",
    "print(\"选中的点的列表为: \",[(x,y) for (x,y) in x[c,:]])\n",
    "tb = PrettyTable()\n",
    "tb.field_names=['points', 'NN', 'NN Distance', 'FN', 'FN Distance']\n",
    "tb.align='l' # 左对齐\n",
    "for i in result:\n",
    "    tb.add_row(i)\n",
    "\n",
    "print(tb)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1fe4a7e2-a8d6-4e62-9ec9-23916459a1cc",
   "metadata": {},
   "source": [
    "#### 参考答案"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "423e7ab2-cbdd-4da7-b711-2b360b85a409",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "从 100 个点中随机挑选 5 个点\n",
      "选中的点的索引值列表为:  [18 60 87 85 44]\n",
      "选中的点的列表为:  [(15, 151), (159, 108), (82, 81), (160, 14), (188, 204)]\n",
      "+---------------+---------------+---------------------+---------------+----------------------+\n",
      "| points        | NN            | NN Distance         | FN            | FN Distance          |\n",
      "+---------------+---------------+---------------------+---------------+----------------------+\n",
      "| ['15' '151']  | ['19' '158']  | ['18<->38' '8.06']  | ['228' '13']  | ['18<->19' '253.80'] |\n",
      "| ['159' '108'] | ['150' '124'] | ['60<->97' '18.36'] | ['18' '244']  | ['60<->11' '195.90'] |\n",
      "| ['82' '81']   | ['91' '78']   | ['87<->23' '9.49']  | ['226' '250'] | ['87<->72' '222.03'] |\n",
      "| ['160' '14']  | ['163' '18']  | ['85<->10' '5.00']  | ['18' '244']  | ['85<->11' '270.30'] |\n",
      "| ['188' '204'] | ['175' '206'] | ['44<->73' '13.15'] | ['9' '11']    | ['44<->48' '263.23'] |\n",
      "+---------------+---------------+---------------------+---------------+----------------------+\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from prettytable import PrettyTable\n",
    "\n",
    "r = np.random.RandomState(seed=30)\n",
    "n = 100\n",
    "x = r.randint(0, 255, (n, 2))       # 生成100个随机点\n",
    "nc = 5\n",
    "c = r.choice(n, nc, replace=False)  # 生成从0到100中随机选择5个点的索引值列表\n",
    "\n",
    "########## 请只修改此范围以内代码 #########\n",
    "h, w = x.shape\n",
    "x1 = x.reshape(h, 1, w)\n",
    "x2 = x.reshape(1, h, w)\n",
    "s = np.sum((x1-x2)**2, axis=2)\n",
    "d = np.argsort(s, axis=1)\n",
    "# 以上代码得到每一个点按距离排序的索引值矩阵 d 【100行，100列】\n",
    "\n",
    "c_list = x[c]  # 得到随机选择的所有点的列表\n",
    "NN_list = x[d[c, 1]]  # 在索引值矩阵d中获得所有选中的点的最近邻，即表示那些点的那一行的第二个元素\n",
    "FN_list = x[d[c, -1]]  # 在索引值矩阵d中获得所有选中的点的最近邻，即表示那些点的那一行的最后一个元素\n",
    "\n",
    "s = np.sqrt(s) # 把距离的平方开方，得到真正的距离\n",
    "\n",
    "# 创造一个N*2的数组\n",
    "# 第一列的元素是 点索引值<->最近邻索引值\n",
    "# 第二列的元素师 点与最近邻的距离\n",
    "NN_dist_sq = np.array(\n",
    "    [[\"{0}<->{1:}\".format(i, d[i, 1]), \"{0:.2f}\".format(s[i, d[i, 1]])] for i in c])\n",
    "\n",
    "# 与上一句逻辑一致，把最近邻改为最远邻\n",
    "FN_dist_sq = np.array(\n",
    "    [[\"{0}<->{1:}\".format(i, d[i, -1]), \"{0:.2f}\".format(s[i, d[i, -1]])] for i in c])\n",
    "\n",
    "result = np.stack((c_list, NN_list, NN_dist_sq, FN_list, FN_dist_sq), axis=1)\n",
    "########################################\n",
    "\n",
    "print(\"从 {0} 个点中随机挑选 {1} 个点\".format(n, nc))\n",
    "print(\"选中的点的索引值列表为: \", c)\n",
    "print(\"选中的点的列表为: \", [(x, y) for (x, y) in x[c, :]])\n",
    "tb = PrettyTable()\n",
    "tb.field_names = ['points', 'NN', 'NN Distance', 'FN', 'FN Distance']\n",
    "tb.align = 'l'\n",
    "for r in result:\n",
    "    tb.add_row(r)\n",
    "\n",
    "print(tb)\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
